package dateStructure;

import sun.management.Agent;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Graph {
    //邻接矩阵+BFS+DFS+迪杰斯特拉算法
    public static void main(String arg[]){
        AGraph MyG=new AGraph();
        MyG=createGraph(MyG);
        System.out.println("----------");
        print(MyG);
//        System.out.println("该邻接矩阵的BFS结果为：");
//        BFS(MyG,0);
        System.out.println("该邻接矩阵的DFS结果为：");
        DFS(MyG,0);
    }
    private static int Maxnum=107;
    private static class AGraph{
        String vex[]=new String[Maxnum];//用于存每一个顶点
        boolean vis[]=new boolean[Maxnum];//定义一个boolean类型数组记录该顶点是否被访问过
        int edge[][]=new int[Maxnum][Maxnum];//用于存每个顶点之间有没有联系
        int vexnum;//用于存顶点的个数
        int edgenum;//用于存顶点间的边数
    }
    private static AGraph createGraph(AGraph g){
        Scanner scanner=new Scanner(System.in);
        System.out.print("请输入顶点的个数和边数：");
        g=new AGraph();
        g.vexnum=scanner.nextInt();
        g.edgenum=scanner.nextInt();
        System.out.print("请依次输入每个顶点：");
        for(int i=0;i<g.vexnum;i++){
            g.vex[i]=scanner.next();//输入vex数组中的每一个顶点的数据
        }
        String v,u;
        int i,j;
        while (g.edgenum-->0){
            System.out.print("请输入有边相连的顶点：");
            //输入两个顶点
            v=scanner.next();
            u=scanner.next();
            i=localGraph(g,v);
            j=localGraph(g,u);
            if(i!=-1&&j!=-1){
                g.edge[i][j]=g.edge[j][i]=1;//如果当前两个顶点在vex数组中存在，即将该两个顶点放入到邻接矩阵中
            }
            else{
                System.out.println("输入中有顶点不存在！");
                g.edgenum++;//如果输入顶点有在vex数组不存在的，即其边数要+1，即减多了的要加回来防止数据丢失
            }
        }
        return g;
    }

    /**
     *
     * @param g
     * @param s 输入的顶点
     * @return 该顶点在vex数组中的索引下标
     */
    public static int localGraph(AGraph g, String s) {
        for (int i = 0; i < g.vexnum; i++) {
            if (g.vex[i].equals(s)) {//如果在全部顶点中找到了要进行判断的顶点
                return i;//返回其索引下标
            }
        }
        return -1;//如果没有找到的话，就返回-1.
    }
    /**
     *
     * @param g 邻接矩阵
     * @param v 广度优先搜索的起点
     */
    private static void BFS(AGraph g,int v){
        LinkedList<Integer> q=new LinkedList<>();//定义一个队列 用于存每次访问的顶点
        q.add(v);//把起点放进队列中去
        g.vis[v]=true;//记录起点已经被访问过了
        int p;//定义一个常量存储每次从队列出队的索引下标
        while (!q.isEmpty()){
            p=q.poll();//从队列中取出队头元素
            System.out.print(g.vex[p]+" ");
            for(int w=0;w<g.vexnum;w++){//遍历所有顶点
                if(g.edge[p][w]==1&&!g.vis[w]){//如果当前的顶点和队列取出的顶点有边相连，同时该顶点还没有被访问过的话
                    g.vis[w]=true;
                    q.add(w);//将其顶点索引下标入队
                }
            }
        }
    }
    /**
     *
     * @param g 邻接矩阵
     * @param v 广度优先搜索的起点
     */
    private static void DFS(AGraph g,int v){
        g.vis[v]=true;//把当前索引下标表示的顶点 标记为访问过的了

        System.out.print(g.vex[v]+" ");

        for(int w=0;w<g.vexnum;w++){//访问全部节点
            if(g.edge[v][w]==1&&!g.vis[w]){//如果当前顶点间有边相连同时该顶点还没有被访问过

                DFS(g,w);//从当前点进行DFS深度搜素

            }
        }
    }
    public static void print(AGraph g){
        System.out.println("该邻接矩阵为：");
        for(int i=0;i<g.vexnum;i++){
            for(int j=0;j<g.vexnum;j++){
                System.out.print(g.edge[i][j]+"\t");
            }
            System.out.println();
        }
    }

}
//class Graph1 {
//    //邻接表+BFS+DFS
//    public static void main(String arg[]) {
//        AGraph MyG = new AGraph();
//        MyG = createGraph(MyG);
//        System.out.println("------------");
//        print(MyG);
////        System.out.println("该邻接表的BFS为：");
////        BFS(MyG,0);
//        System.out.println("该邻接表的DFS为：");
//        DFS(MyG,0);
//    }
//
//    private static int Maxnum = 107;
//    private static class Graphnode {
//        String data;//用于存每个顶点的数据 既名字
//        int val;//用于存每个顶点的索引下标
//        Graphnode next;//用于存顶点链表中每个结点的下一个
//    }
//
//    private static class AGraph {
//        boolean vis[]=new boolean[Maxnum];
//        Graphnode vex[] = new Graphnode[Maxnum];//用于存每一个顶点
//        int vexnum;//用于存顶点的个数
//        int edgenum;//用于存顶点间的边数
//    }
//
//    private static AGraph createGraph(AGraph g) {
//        Scanner scanner = new Scanner(System.in);
//        System.out.print("请输入顶点的个数和边数：");
//        g.vexnum = scanner.nextInt();
//        g.edgenum = scanner.nextInt();
//        System.out.print("请依次输入每个顶点：");
//        for (int i = 0; i < g.vexnum; i++) {
//            g.vex[i]=new Graphnode();//**每次输入都要实例化一下！别忘记了！
//            g.vex[i].data = scanner.next();//输入vex数组中的每一个顶点的数据
//            g.vex[i].val=i;
//        }
//        String v, u;
//        int i, j;
//        while (g.edgenum-- > 0) {
//            System.out.print("请输入有边相连的顶点：");
//            //输入两个顶点
//            v = scanner.next();
//            u = scanner.next();
//            i = localGraph(g, v);//获得顶点在vex数组中的索引下标
//            j = localGraph(g, u);//获得顶点在vex数组中的索引下标
//            if (i != -1 && j != -1) {
//                insertGraph(g, i, j);//如果当前两个顶点在vex数组中存在，就把第二个结点插入到第一个结点后面的链表中
//            } else {
//                System.out.println("输入中有顶点不存在！");
//                g.edgenum++;//如果输入顶点有在vex数组不存在的，即其边数要+1，即边数减多了的要加回来防止数据丢失
//            }
//        }
//        return g;
//    }
//
//    /**
//     *
//     * @param g 邻接表
//     * @param i 头结点的索引下标
//     * @param j 邻接节点的索引下标
//     */
//    private static void insertGraph(AGraph g, int i, int j) {
//        //头插法
//        Graphnode x = new Graphnode();//建立一个新的结点
//        x.data = g.vex[j].data;//把第二个结点的名字赋给新节点的data
//        x.val=j;//把第二个结点的索引下标赋给新节点的val
//        x.next = g.vex[i].next;//当前结点的下一个地址赋值给新建结点的下一个
//        g.vex[i].next = x;//把新建结点赋值给当前结点的下一个地址
//    }
//    /**
//     *
//     * @param g
//     * @param s 输入的顶点
//     * @return 该顶点在vex数组中的索引下标
//     */
//    public static int localGraph(AGraph g, String s) {
//        for (int i = 0; i < g.vexnum; i++) {
//            if (g.vex[i].data.equals(s)) {//如果在全部顶点中找到了要进行判断的顶点
//                return i;//返回其索引下标
//            }
//        }
//        return -1;//如果没有找到的话，就返回-1.
//    }
//    public static void print(AGraph g) {
//        System.out.println("该邻接表为：");
//        for (int i = 0; i < g.vexnum; i++) {
//            System.out.print(g.vex[i].data + ":");//输出当前顶点
//            Graphnode x = g.vex[i].next;//将当前顶点后面的链表输出
//            if(x==null){//如果为空
//                System.out.print("->null");
//            }
//            while (x != null) {
//                System.out.print("->" + x.data + " ");//输出链表中每个节点中的索引小标 表示该顶点和这些下标所指的顶点有边相连
//                x = x.next;//继续往下走
//            }
//            System.out.println();
//        }
//    }
//    /**
//     *
//     * @param g 邻接表
//     * @param v 广度优先搜索的起点
//     */
//    private static void BFS(AGraph g,int v){
//        LinkedList<Integer> q=new LinkedList<>();//定义一个队列 用于存储每次访问的顶点
//        q.add(g.vex[v].val);//把起点放进队列中去******一定要把该数值v所代表的索引的数值放进去！！！！
//        g.vis[g.vex[v].val]=true;//记录起点已经被访问过了
//        int p;//定义一个常量存储每次从队列出队的索引下标
//
//        while (!q.isEmpty()){//判断队列是否为空
//
//            p=q.poll();//取出队头元素既索引下标
//            System.out.print(g.vex[p].data+"\t");//输出当前从队头取出索引下标对应顶点的数据
//
//            while (g.vex[p]!=null){//如果从队头取出的索引下标对应的顶点节点不为空的话
//
//                if(!g.vis[g.vex[p].val]){//如果当前出队的索引下标对应顶点没有被访问过的话
//                    q.add(g.vex[p].val);//将该顶点入队
//                    g.vis[g.vex[p].val]=true;//同时标记当前顶点已经被访问过了
//                }
//
//                g.vex[p]=g.vex[p].next;//指针继续往下走
//            }
//        }
//    }
//
//    /**
//     *
//     * @param g 邻接表
//     * @param v DFS开始的起始点
//     */
//    private static void DFS(AGraph g,int v){
//        g.vis[v]=true;//标记当前顶点已经访问过了
//
//        System.out.print(g.vex[v].data+" ");
//
//        Graphnode x=g.vex[v].next;//将当前顶点指向下一个的指针赋值给x
//
//        while (x!=null){//如果x不为空
//            if(!g.vis[x.val]){//如果当前顶点下标所对应的顶点没有被访问过
//                DFS(g,x.val);//对该顶点进行DFS深度搜素
//            }
//            x=x.next;//向下循环
//        }
//    }
//}
class Graph3{
    //邻接矩阵+dijkstra算法
    public static void main(String arg[]){
        Scanner scanner=new Scanner(System.in);
        AGraph MyG=new AGraph();
        MyG=createGraph(MyG);
        System.out.print("请输入起始点的信息：");
        String u=scanner.nextLine();
        int v=localGraph(MyG,u);
        Dijkstra(MyG,v);
        System.out.println("起始点的位置为："+u);
        for(int i=0;i<MyG.vexnum;i++){
            System.out.print(u+"要去的位置是："+MyG.vex[i]);
            if(MyG.dist[i]==INF){
                System.out.println("无路可走！");
            }
            else{
                System.out.println("最短路径为："+MyG.dist[i]);
            }
        }
        findPath(MyG,u);
    }
    private static final int INF= Integer.MAX_VALUE;//定义一个最大值常量
    private static final int Maxnum=107;
    private static class AGraph{
        int dist[]=new int[Maxnum];//定义一个数组记录最短路径
        int p[]=new int[Maxnum];//定义一个数组记录当前顶点的前驱
        String vex[]=new String[Maxnum];//用于存每一个顶点
        boolean vis[]=new boolean[Maxnum];//定义一个boolean类型数组记录该顶点是否被访问过
        int edge[][]=new int[Maxnum][Maxnum];//用于存每个顶点之间有没有联系****存的是顶点 不是索引号！！
        int vexnum;//用于存顶点的个数
        int edgenum;//用于存顶点间的边数
        int weight;//用于记录两个顶点间的权值
    }
    private static AGraph createGraph(AGraph g){
        Scanner scanner=new Scanner(System.in);
        System.out.print("请输入顶点的个数和边数：");
        g=new AGraph();
        g.vexnum=scanner.nextInt();
        g.edgenum=scanner.nextInt();
        System.out.print("请依次输入每个顶点：");
        for(int i=0;i<g.vexnum;i++){
            g.vex[i]=scanner.next();//输入vex数组中的每一个顶点的数据
            for(int j=0;j<g.vexnum;j++){
                g.edge[i][j]=INF;
            }
        }
        String v,u;
        int i,j;
        while (g.edgenum-->0){
            //输入两个顶点t
            System.out.print("请输入有边相连的顶点与其边的权值：");
            v=scanner.next();
            u=scanner.next();
            g.weight=scanner.nextInt();
            i=localGraph(g,v);
            j=localGraph(g,u);
            if(i!=-1&&j!=-1){
                g.edge[i][j]=g.weight;//如果当前两个顶点在vex数组中存在，即将该两个顶点放入到邻接矩阵中
            }
            else{
                System.out.println("输入中有顶点不存在！");
                g.edgenum++;//如果输入顶点有在vex数组不存在的，即其边数要+1，即减多了的要加回来防止数据丢失
            }
        }
        return g;
    }

    /**
     *
     * @param g
     * @param s 输入的顶点
     * @return 该顶点在vex数组中的索引下标
     */
    public static int localGraph(AGraph g, String s) {
        for (int i = 0; i < g.vexnum; i++) {
            if (g.vex[i].equals(s)) {//如果在全部顶点中找到了要进行判断的顶点
                return i;//返回其索引下标
            }
        }
        return -1;//如果没有找到的话，就返回-1.
    }

    /**
     *
     * @param g 邻接矩阵
     * @param u 算法开始的起始点
     */
    private static void Dijkstra(AGraph g,int u){
        //初始化过程
        for(int i=0;i<g.vexnum;i++){
            g.dist[i]=g.edge[u][i];//初始化最短路径
            if(g.dist[i]!=INF){//如果当前节点到起始点有路径
                g.p[i]=u;//更新该顶点的前驱为起始点
            }
            else{
                g.p[i]=-1;//否则当前顶点没有前驱
            }
        }
        g.vis[u]=true;//标记起始点已经访问过
        g.dist[u]=0;//起始点的最短路径为0

        //Dijkstra算法开始
        for(int i=0;i<g.vexnum;i++){
            int temp=INF;//定义一个临时变量 一开始初始化为INF
            int t=u;//定义一个变量记录起始节点

            for(int j=0;j<g.vexnum;j++){//开始寻找当前顶点的最短路径
                if(!g.vis[j]&&g.dist[j]<temp){//如果找到有未被访问过同时比之前找到的路径短的顶点
                    temp=g.dist[j];//更新最短路径的中间值
                    t=j;//将当前的顶点赋值给中间值
                }
            }
            if(t==u){//如果当前顶点没有被更新的话，说明找不到，直接返回
                return;
            }
            g.vis[t]=true;//如果找到了，标记当前顶点已经被访问

            for(int j=0;j<g.vexnum;j++){
                if(!g.vis[j]&&g.edge[t][j]<INF){
                    //*****注意这里的g.edge[t][j]千万不要写成g.dist[j]因为这个时候t已经更新了，而g.dist[j]可能还没有更新，还有可能是到原点距离，就不对了！！！！

                    if(g.dist[j]>(g.dist[t]+g.edge[t][j])){//如果发现到达当前顶点的路径有更优的解

                        g.dist[j]=g.dist[t]+g.edge[t][j];//更新当前最短路径
                        g.p[j]=t;//更新当前顶点的前驱
                    }
                }
            }
        }
    }

    /**
     *
     * @param g 邻接矩阵
     * @param u 起始点的信息
     */
    private static void findPath(AGraph g,String u){
        LinkedList<Integer> s=new LinkedList<>();
        int x;
        for(int i=0;i<g.vexnum;i++){
            x=g.p[i];//定义一个常量存储当前顶点的前驱
            if(x==-1&&!g.vex[i].equals(u)){//如果当前顶点没有前驱或者当前顶点没有在集合顶点中
                continue;//继续往下走
            }
            while (x!=-1){//如果x存在前驱
                s.push(x);//讲x逆序入栈
                x=g.p[x];//将x的前驱赋值给x
            }
            System.out.print("起始点:"+u+"到各个顶点的最短路径为：");
            while (!s.isEmpty()){
                System.out.print(g.vex[s.pop()]+"->");//输出路径中的每个顶点
            }
            System.out.print(g.vex[i]);//输出当前顶点，因为是倒序输出，所以当前顶点最后输出
            System.out.println("该最短路径的距离为："+g.dist[i]);
        }
    }
}
//class Graph4 {
//    Floyd算法
//    public static void main(String arg[]) {
//        Scanner scanner = new Scanner(System.in);
//        AGraph MyG = new AGraph();
//        MyG = createGraph(MyG);
//        Floyd(MyG);
//        print(MyG);
//        System.out.print("请以此输入起点和终点名称：");
//        String u = scanner.next();
//        String v = scanner.next();
//        int i = localGraph(MyG, u);
//        int j = localGraph(MyG, v);
//        System.out.print("这两个顶点的最短路径为：");
//        displayPath(MyG, i, j);
//        System.out.println(MyG.vex[j]);
//        System.out.println("该最短路径的最短长度为：" + MyG.dist[i][j]);
//    }
//
//    private static final int Maxnum = 107;
//    private static final int INF = 100007; //ps：涉及最大值 千万不要用Integer.MAX_VALUE！！！单纯比较才可以
//
//    private static class AGraph {
//        int dist[][] = new int[Maxnum][Maxnum];//定义一个数组记录最短路径
//        int p[][] = new int[Maxnum][Maxnum];//定义一个二维数组 来记录当前这两个顶点间这条边的前驱
//        String vex[] = new String[Maxnum];//用于存每一个顶点
//        int edge[][] = new int[Maxnum][Maxnum];//用于存每个顶点之间有没有联系****存的是顶点 不是索引号！！
//        int vexnum;//用于存顶点的个数
//        int edgenum;//用于存顶点间的边数
//        int weight;//用于记录两个顶点间的权值
//    }
//
//    private static AGraph createGraph(AGraph g) {
//        Scanner scanner = new Scanner(System.in);
//        System.out.print("请输入顶点的个数和边数：");
//        g.vexnum = scanner.nextInt();
//        g.edgenum = scanner.nextInt();
//        System.out.print("请依次输入每个顶点：");
//        for (int i = 0; i < g.vexnum; i++) {
//            g.vex[i] = scanner.next();//输入vex数组中的每一个顶点的数据
//        }
//        for (int i = 0; i < g.vexnum; i++) {
//            for (int j = 0; j < g.vexnum; j++) {
//                if (i != j) {
//                    g.edge[i][j] = INF;
//                } else {
//                    g.edge[i][j] = 0;
//                }
//            }
//        }
//        String v, u;
//        int i, j;
//        while (g.edgenum-- > 0) {
//            //输入两个顶点t
//            System.out.print("请输入有边相连的顶点与其边的权值：");
//            v = scanner.next();
//            u = scanner.next();
//            g.weight = scanner.nextInt();
//            i = localGraph(g, v);
//            j = localGraph(g, u);
//            if (i != -1 && j != -1) {
//                g.edge[i][j] = g.weight;//如果当前两个顶点在vex数组中存在，即将该两个顶点放入到邻接矩阵中
//            } else {
//                System.out.println("输入中有顶点不存在！");
//                g.edgenum++;//如果输入顶点有在vex数组不存在的，即其边数要+1，即减多了的要加回来防止数据丢失
//            }
//        }
//        return g;
//    }
//
//    /**
//     * @param g
//     * @param s 输入的顶点
//     * @return 该顶点在vex数组中的索引下标
//     */
//    public static int localGraph(AGraph g, String s) {
//        for (int i = 0; i < g.vexnum; i++) {
//            if (g.vex[i].equals(s)) {//如果在全部顶点中找到了要进行判断的顶点
//                return i;//返回其索引下标
//            }
//        }
//        return -1;//如果没有找到的话，就返回-1.
//    }
//
//    /**
//     * @param g 邻接矩阵
//     * @param u 第一个顶点
//     * @param v 第二个顶点
//     */
//    public static void displayPath(AGraph g, int u, int v) {
//        if (g.p[u][v] != -1) {//如果当前两个顶点之间有前驱的话
//            displayPath(g, u, g.p[u][v]);//继续往前走
//            System.out.print(g.p[u][v] + "->");//输出路径中的每个顶点
//        }
//    }
//
//    private static void Floyd(AGraph g) {
//        //先进行初始化过程：
//        for (int i = 0; i < g.vexnum; i++) {
//            for (int j = 0; j < g.vexnum; j++) {
//                g.dist[i][j] = g.edge[i][j];
//                if (g.dist[i][j] != INF && i != j) {//如果当前两个顶点间有权值，同时不是同一个顶点的情况下
//                    g.p[i][j] = i;//把该两个顶点的前驱设为第一个顶点
//                } else {
//                    g.p[i][j] = -1;//否则该两个顶点没有前驱
//                }
//            }
//        }
//        //Floyd算法开始！
//        for (int k = 0; k < g.vexnum; k++) {
//            for (int i = 0; i < g.vexnum; i++) {
//                for (int j = 0; j < g.vexnum; j++) {
//
//                    if (g.dist[i][j] > (g.dist[i][k] + g.dist[k][j])) {//如果发现当前i j两个顶点通过插点k可以实现更短的距离
//
//                        g.dist[i][j] = g.dist[i][k] + g.dist[k][j];//则更新最短距离
//                        g.p[i][j] = g.p[k][j];//同时记录当前两个顶点的前驱
//                    }
//                }
//            }
//        }
//    }
//
//    private static void print(AGraph g) {
//        System.out.println("该图的最短距离矩阵为：");
//        for (int i = 0; i < g.vexnum; i++) {
//            for (int j = 0; j < g.vexnum; j++) {
//                System.out.print(g.dist[i][j] + "\t");
//            }
//            System.out.println();
//        }
//        System.out.println("------------");
//        System.out.println("该图的各个顶点间的前驱矩阵为：");
//        for (int i = 0; i < g.vexnum; i++) {
//            for (int j = 0; j < g.vexnum; j++) {
//                System.out.print(g.p[i][j] + "\t");
//            }
//            System.out.println();
//        }
//    }
//}
//class Graph5 {
//    //Prim算法
//    public static void main(String arg[]) {
//        Scanner scanner = new Scanner(System.in);
//        AGraph MyG = new AGraph();
//        MyG = createGraph(MyG);
//        System.out.print("请输入任一个顶点作为起始点：");
//        int v = scanner.nextInt()-1;
//        Prim(MyG, v);
//        print(MyG);
//    }
//
//    private static final int Maxnum = 107;//设置一个顶点的最大值
//    private static final int INF = 100007; //ps：涉及最大值 千万不要用Integer.MAX_VALUE！！！单纯比较才可以
//
//    private static class AGraph {
//        int lowcost[] = new int[Maxnum];//定义一个lowcost数组记录U集合到U-V集合的最短距离
//        int closet[] = new int[Maxnum];//定义一个closet数组来记录当前顶点到U集合最短距离的一个顶点，也可以说是为其前驱
//        int edge[][] = new int[Maxnum][Maxnum];//用于存每个顶点之间有没有联系****存的是顶点 不是索引号！！
//        boolean vis[]=new boolean[Maxnum];//定义一个Boolean数组记录当前顶点是否被访问过了
//        int vexnum;//用于存顶点的个数
//        int edgenum;//用于存顶点间的边数
//        int weight;//用于记录两个顶点间的权值
//    }
//
//    private static AGraph createGraph(AGraph g) {
//        Scanner scanner = new Scanner(System.in);
//        System.out.print("请依次输入图的顶点数和边数：");
//        g.vexnum = scanner.nextInt();
//        g.edgenum = scanner.nextInt();
//        for(int i=0;i<g.vexnum;i++){
//            for(int j=0;j<g.vexnum;j++){
//                g.edge[i][j]=INF;
//            }
//        }
//        System.out.println("请依次输入每条边的顶点数和其边的权值");
//        while (g.edgenum-- > 0) {//输入其各个边和其权值
//            int i = scanner.nextInt()-1;
//            int j = scanner.nextInt()-1;
//            g.weight = scanner.nextInt();
//            g.edge[i][j]=g.edge[j][i] = g.weight;//因为是无向图所以对称两个点都要看
//        }
//        return g;
//    }
//
//    /**
//     *
//     * @param g 所要遍历的图
//     * @param v 输入 选择的起始点
//     */
//    private static void Prim(AGraph g, int v) {
//        for(int i=0;i<g.vexnum;i++){//初始化过程
//            g.lowcost[i]=g.edge[v][i];
//            if(g.lowcost[i]<INF){//如果当前顶点与起始点之间有边相连
//                g.closet[i]=v;//当前顶点离集合U最近的点就为起始点
//            }
//            else{
//                g.closet[i]=-1;//否则就没有离集合最近的点
//            }
//        }
//        g.vis[v]=true;//讲起始点放入到集合U中
//        g.lowcost[v]=0;//起始点在集合U中，到集合中的距离为0
//        //Prim算法开始
//        for(int i=0;i<g.vexnum;i++){
//            int temp=INF;
//            int t=v;
//            for(int j=0;j<g.vexnum;j++){
//                if(!g.vis[j]&&g.lowcost[j]<temp){//在集合中找到离集合U相离最短的距离的顶点
//                    temp=g.lowcost[j];
//                    t=j;//更新最新的顶点
//                }
//            }
//            if(t==v){//如果没有找到当前顶点的话，就返回
//                return;
//            }
//            g.vis[t]=true;//将当前找到的顶点放入到集合U中去
//            for(int j=0;j<g.vexnum;j++){
//                if(!g.vis[j]&&g.edge[t][j]<g.lowcost[j]){//寻找一下，看看能否从当前的顶点中找到有更短的距离
//                    g.lowcost[j]=g.edge[t][j];//找到了则赋值到lowcost数组
//                    g.closet[j]=t;//同时更新closet数组，即当前顶点到集合中最近的顶点为t
//                }
//            }
//        }
//
//    }
//    private static void print(AGraph g){
//        int tot=0;
//        System.out.print("lowcost数组的值为：");
//        for(int i=0;i<g.vexnum;i++){
//            tot+=g.lowcost[i];//将每个顶点的最短路径的长度加起来
//            System.out.print(g.lowcost[i]+" ");
//        }
//        System.out.println();
//        System.out.print("最短路径的长度为："+tot);
//    }
//}
//class Graph6 {
//kruskal算法
//    public static void main(String arg[]) {
//        Scanner scanner = new Scanner(System.in);
//        System.out.print("请输入图的顶点数和边数：");
//        n = scanner.nextInt();
//        m = scanner.nextInt();
//        init(n);
//        System.out.println("请依次输入每条边的两个顶点与其权值：");
//        for (int i = 0; i < m; i++) {
//            edge[i] = new Edge();
//            edge[i].u = scanner.nextInt() - 1;
//            edge[i].v = scanner.nextInt() - 1;
//            edge[i].weight = scanner.nextInt();
//        }
//        List<Edge> list = Arrays.asList(edge).stream().filter(e -> e != null).sorted((e1, e2) -> e1.weight - e2.weight).collect(Collectors.toList());
//        edge = new Edge[list.size()];
//        edge = list.toArray(edge);
//        System.out.println("最小花费为：" + Kruskal(n));
//    }
//
//    private static final int Maxnum = 107;
//    private static Edge edge[] = new Edge[Maxnum * Maxnum];
//    private static int n, m;//顶点数和边数
//    private static int nodes[] = new int[Maxnum];//开一个数组记录每条边的权值
//
//    private static class Edge {
//        int u;
//        int v;
//        int weight;//每条边的权值
//    }
//
//    public static void init(int n) {
//        //初始化
//        for (int i = 0; i < n; i++) {
//            nodes[i] = i;//将每个节点的值初始化为其索引号
//        }
//    }
//    /**
//     * @param n 是当前图中顶点的个数
//     */
//    private static int Kruskal(int n) {
//        //Kruskal算法开始
//        int tot = 0;//记录当前所有找到的顶点的权值和
//        System.out.print("所选边的权值为：");
//        for (int i = 0; i < m; i++) {
//            if (merge(edge[i].u, edge[i].v)) {//如果判断到当前的边没有形成圈
//                tot += edge[i].weight;//就把当前的边的权值加进去
//                System.out.print(edge[i].weight+" ");
//                n--;//找到了就把边的数目减一
//                if (n == 1) {
//                    System.out.println();
//                    return tot;//返回权值总数
//                }
//            }
//        }
//        System.out.println();
//        return 0;
//    }
//
//    /**
//     * @param a 第一条边的索引号
//     * @param b 第二条边的索引号
//     * @return 是否形成了圈
//     */
//    public static boolean merge(int a, int b) {
//        if (nodes[a] == nodes[b]) {//如果当前两个顶点的索引号相同，即形成了圈
//            return false;
//        }
//        for (int i = 0; i < n; i++) {
//            if (nodes[i] == nodes[b]) {//如果当前边的集合号等于a的集合号
//                nodes[i] = nodes[a];//就把他赋值给b的集合号
//            }
//        }
//        return true;
//    }
//
//}
class Graph7 {
    //邻接表的拓扑排序+关键路径

    /**
     * 6 8
     * C0 C1 C2 C3 C4 C5
     * C0 C1
     * C0 C2
     * C0 C3
     * C2 C1
     * C2 C4
     * C3 C4
     * C5 C3
     * C5 C4
     */

    /**
     6 8
     V0 V1 V2 V3 V4 V5
     V0 V1 2
     V0 V2 15
     V1 V4 19
     V1 V3 10
     V2 V1 4
     V2 V4 11
     V3 V5 6
     V4 V5 5
     */
    public static void main(String arg[]) {
        AGraph MyG = new AGraph();
        createGraph(MyG);
        print(MyG);
        criticalPath(MyG);
    }

    private static final int Maxnum = 107;

    private static class AGraphnode {
        AGraphnode next;//定义一个指针用于连接邻接表中的每一个顶点
        String data;//记录每个顶点的名称
        int val;//记录每个顶点的索引下标
        int weight;//记录当前事件的权值
    }

    private static class AGraph {
        AGraphnode vex[] = new AGraphnode[Maxnum];//定义一个邻接表
        AGraphnode rvex[] = new AGraphnode[Maxnum];//定义一个逆邻接表
        int indegree[] = new int[Maxnum];//定义一个数组用于记录每个顶点的入度
        int top[] = new int[Maxnum];//定义一个数组用于记录最后拓扑排序的结果
        int ve[] = new int[Maxnum];
        int vl[] = new int[Maxnum];
        int edgenum;//记录弧的个数
        int vexnum;//记录顶点的个数
    }

    private static void createGraph(AGraph g) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请依次输入顶点数和边的个数：");
        g.vexnum = scanner.nextInt();
        g.edgenum = scanner.nextInt();
        System.out.print("请依次输入各个顶点：");
        for (int i = 0; i < g.vexnum; i++) {
            g.vex[i] = new AGraphnode();
            g.rvex[i] = new AGraphnode();
            g.vex[i].data = scanner.next();
            g.rvex[i].data = g.vex[i].data;
        }
        System.out.println("请依次输入每条边的两个顶点：");
        while (g.edgenum-- > 0) {
            String u = scanner.next();
            String v = scanner.next();
            int w=scanner.nextInt();
            int i = localGraph(g, u);
            int j = localGraph(g, v);
            if (i != -1 && j != -1) {//如果输入的两个顶点都在顶点集合里的话
                insertGraph(g, i, j,w);//讲两个顶点插入到邻接表中
            } else {
                g.edgenum++;//否则的话就把当前减少的边数加回去
            }
        }
    }

    private static void insertGraph(AGraph g, int i, int j,int w) {
        //插入到邻接表中
        AGraphnode x1 = new AGraphnode();
        x1.data = g.vex[j].data;
        x1.val = j;
        x1.next = g.vex[i].next;//运用头插法
        g.vex[i].next = x1;
        x1.weight=w;

        //插入到逆邻接表中
        AGraphnode x2 = new AGraphnode();
        x2.data = g.rvex[i].data;
        x2.val = i;
        x2.next = g.rvex[j].next;//运用头插法
        g.rvex[j].next = x2;
        x2.weight=w;
    }

    private static void findIndegree(AGraph g) {
        System.out.print("该图每个顶点的入度为：");
        for (int i = 0; i < g.vexnum; i++) {
            int sum = 0;//定义一个常量用于记录每个顶点的入度
            AGraphnode x = g.rvex[i].next;
            while (x != null) {
                sum++;
                x = x.next;
            }
            g.indegree[i] = sum;//将当前统计到的入度赋值到入度数组中
            System.out.print(g.indegree[i] + " ");
        }
        System.out.println();
    }

    private static boolean topologicalSort(AGraph g) {
        //拓扑排序开始
        LinkedList<Integer> s = new LinkedList<>();//定义一个栈，放入每一个已经删除入度的顶点
        findIndegree(g);
        for (int i = 0; i < g.vexnum; i++) {
            if (g.indegree[i] == 0) {//寻找一开始入度为0的顶点，放入到栈中
                s.push(i);
            }
        }
        int m = 0;
        int p;
        while (!s.isEmpty()) {
            p = s.pop();
            g.top[m++] = p;//将从栈中弹出的顶点放入到拓扑排序后的数组中
            AGraphnode x = g.vex[p].next;//找到与该顶点所相连的顶点
            while (x != null) {
                int k = x.val;//记录当前顶点的索引下标
                g.indegree[k]--;//将其每一个相连的顶点的入度都减一
                if (g.indegree[k] == 0) {
                    s.push(k);//如果发现有顶点的入度为0了，就入栈
                }
                x = x.next;//继续向下搜寻
            }
        }
        return m < g.vexnum ? false : true;//如果最后拓扑排序后的数组中的个数少于总顶点数，则说明该图中存在环，则不存在拓扑排序的结果
    }

    public static void print(AGraph g) {
        System.out.println("该图的邻接表为：");
        for (int i = 0; i < g.vexnum; i++) {
            System.out.print(g.vex[i].data + ": ");
            AGraphnode x = g.vex[i].next;
            while (x != null) {
                System.out.print("[" + x.val + "] ");
                x = x.next;
            }
            System.out.println();
        }
        System.out.println("----------------");
        System.out.println("该图的逆邻接表为：");
        for (int i = 0; i < g.vexnum; i++) {
            System.out.print(g.rvex[i].data + ": ");
            AGraphnode x = g.rvex[i].next;
            while (x != null) {
                System.out.print("[" + x.val + "] ");
                x = x.next;
            }
            System.out.println();
        }
    }

    private static int localGraph(AGraph g, String s) {
        for (int i = 0; i < g.vexnum; i++) {
            if (g.vex[i].data.equals(s)) {//如果找到有相同的顶点
                return i;//返回其索引下标
            }
        }
        return -1;
    }

    private static void criticalPath(AGraph g) {
        if (topologicalSort(g)) {
            System.out.print("该图的拓扑排序结果为：");
            for (int i = 0; i < g.vexnum; i++) {
                System.out.print(g.vex[g.top[i]].data + " ");
            }
            System.out.println();
        } else {
            System.out.println("该图没有拓扑排序结果！");
        }

        for(int i=0;i<g.vexnum;i++){
            g.ve[i]=0;//先进行初始化，将所有事件的最早发生时间初始化为0
        }
        int k,p;
        for(int i=0;i<g.vexnum;i++){
            k=g.top[i];//用正序拓扑排序来进行找寻，取出当前节点在拓扑排序中的索引号
            AGraphnode x=g.vex[k].next;//通过邻接表来找寻每个事件的最早发生时间
            while (x!=null){
                p=x.val;
                if(g.ve[k]+x.weight>g.ve[p]){//找到最大的一条路径，更新为当前事件的最早发生时间
                    g.ve[p]=g.ve[k]+x.weight;
                }
                x=x.next;
            }
        }

        for(int i=0;i<g.vexnum;i++){
            g.vl[i]=g.ve[g.vexnum-1];//将每个事件的最迟发生时间初始化为最后一个顶点的最早发生时间
        }
        for(int i=g.vexnum-1;i>=0;i--){
            k=g.top[i];//用正序拓扑排序来进行找寻，取出当前节点在拓扑排序中的索引号
            AGraphnode x=g.vex[k].next;
            while (x!=null){
                p=x.val;
                if(g.vl[p]-x.weight<g.vl[k]){//找到一条最小的路径，更新为当前事件的最迟发生时间
                    g.vl[k]=g.vl[p]-x.weight;
                }
                x=x.next;
            }
        }
        System.out.println("每个事件的最早发生时间和最晚发生时间为：");
        for(int i=0;i<g.vexnum;i++){
            System.out.println(g.ve[i]+" "+g.vl[i]);
        }
        System.out.println("关键路径的权值之和为："+g.vl[g.vexnum-1]);
        System.out.println("关键路径为：");
        for(int i=0;i<g.vexnum;i++){
            AGraphnode x=g.vex[i].next;
            while (x!=null){
                k=x.val;
                int e=g.ve[i];//当前事件的最早发生时间
                int l=g.vl[k]-x.weight;//当前事件的最迟发生时间
                if(e==l){//如果当前事件的最早发生时间和其最迟发生时间相同的话，则说明为关键活动
                    System.out.print("<"+g.vex[i].data+","+g.vex[k].data+"> ");//输出当前关键路径
                }
                x=x.next;
            }
        }
        System.out.println();
    }
}